#include "mainwindow.h"
#include "ui_mainwindow.h"
#include <QString>
#include <qstring.h>
#include <QDebug>
#include <string.h>
#include <string>
#include <algorithm>
#include "e.h"
#include "id.h"
#include <math.h>
int n;
int rn;
int m=0;
int flag;
int pflag=0;
int cost;
int e[1000];
int father[100];
struct edge E[1000];
struct vposition V[100];
int vertexnum;
bool cmp(edge a, edge b){
    return a.cost < b.cost;
}
int findFather(int x)
{
    if(father[x] == x)
        return x;
    else
        father[x] = findFather(father[x]);
    return father[x];
}

void kruskal()
{
    int Num_Edge = 0;
    int step=0;
    for(int i = 0; i < n; ++i){
        father[i] = i;
    }
    std::sort(E, E + m, cmp);
    for(int i = 0; i < m; ++i){
        int faU = findFather(E[i].u);
        int faV = findFather(E[i].v);
        if(faU != faV)//判断两边的顶点是否为同一父节点
        {
            father[faU] = faV;
            cost += E[i].cost;
            e[step]=i;
            Num_Edge++;
            if(Num_Edge == n - 1) break;
            step++;
        }
    }
}
MainWindow::MainWindow(QWidget *parent)
    : QMainWindow(parent)
    , ui(new Ui::MainWindow)
{
    ui->setupUi(this);
    w2.setWindowTitle("动态演示");
    QPalette palette(w2.palette());
    palette.setColor(QPalette::Background, QColor("green"));
    w2.setAutoFillBackground(true);
    w2.setPalette(palette);
    connect(ui->pok, &QPushButton::clicked, this, &MainWindow::changewin);
}
void prim()
{
    int i,j;
    bool b[n];
    memset(b,true,sizeof(b));
    std::sort(E, E + m, cmp);
    int c=E[0].u;
    b[c]=false;
    int f=E[0].v;
    for(i=0;i<n-1;i++)
    {
       for(j=0;j<m;j++)
       {
           if((b[E[j].u]==false)&&(b[E[j].v]==true))
           {
                c=E[j].u;
                f=E[j].v;
                b[f]=false;
                cost+=E[j].cost;
                e[i]=j;
                break;
            }
        }
    }
}
void MainWindow::randomgraph()
{
    float d[n][n];
    for(int i=0;i<n;i++)
    {
        V[i].x=rand()%520+40;
        V[i].y=rand()%460+60;
        for(int j=0;j<i;j++)
        {
            while(1)
            {
                float xr=(V[i].x-V[j].x)*(V[i].x-V[j].x);
                float yr=(V[i].y-V[j].y)*(V[i].y-V[j].y);
                d[i][j]=sqrt(xr+yr);
                if(d[i][j]>=80)
                {
                    break;
                }
                V[i].x=rand()%520+40;
                V[i].y=rand()%460+60;
            }
        }
    }
    int cn=0;
    for(int i=0;i<n-1;i++)
    {
        cn=0;
         for(int j=i+1;j<n;j++)
         {
             float xr=(V[i].x-V[j].x)*(V[i].x-V[j].x);
             float yr=(V[i].y-V[j].y)*(V[i].y-V[j].y);
             d[i][j]=sqrt(xr+yr);
              if(d[i][j]>300)
              {
                  E[m*2].u=i;
                  E[m*2].v=j;
                  E[m*2].cost=(int)d[i][j];
                  E[m*2+1].v=E[m*2].u;
                  E[m*2+1].u=E[m*2].v;
                  E[m*2+1].cost=(int)d[i][j];
                  m++;
                  cn++;
              }
         }
         if(cn==0)
         {
             E[m*2].u=i;
             E[m*2].v=(i+1)%n;
             E[m*2].cost=250;
             E[m*2+1].v=E[m*2].u;
             E[m*2+1].u=E[m*2].v;
             E[m*2+1].cost=250;
             m++;
         }
    }
    m=2*m;
}

MainWindow::~MainWindow()
{
    delete ui;
}
void MainWindow::on_pok_clicked()
{
    this->close();
    if(pflag==0){
        QString na=ui->ln->text();
        n=na.toInt();
        QString ma=ui->lm->text();
        m=ma.toInt();
        QString ta=ui->tc->toPlainText();
        ta=ta.simplified();
        QStringList qa=ta.split(" ");
        for (int i=0;i<m;i++) {
            E[2*i].u=qa[3*i].toInt();
            E[2*i].v=qa[3*i+1].toInt();
            E[2*i].cost=qa[3*i+2].toInt();
            E[2*i+1].u=E[2*i].v;
            E[2*i+1].v=E[2*i].u;
            E[2*i+1].cost=E[2*i].cost;
        }
        int xs[10]={35,35,525,525,280,280,140,140,420,420};
        int ys[10]={35,545,545,35,100,500,175,435,175,435};
        for (int i=0;i<n;i++)
        {
            V[i].x=xs[i];
            V[i].y=ys[i];
        }
       m=2*m;
    }
   QString ca=ui->cpk->currentText();
   if(ca.operator==("prim算法"))
   {
       if(pflag==0)
       {
           flag=0;
           prim();
       }
       if(pflag==1)
       {
           n=rn;
           randomgraph();
           flag=2;
       }
   }
   if(ca.operator==("kruskal算法"))
   {
       if(pflag==0)
       {
           flag=1;
           kruskal();
       }
       if(pflag==1)
       {
           n=rn;
           randomgraph();
           flag=3;
       }
   }
   bool isvertex[100];
   memset(isvertex,false,sizeof(isvertex));
   for(int i=0;i<m;i+=2)
   {
       isvertex[E[i].u]=true;
       isvertex[E[i].v]=true;
   }
   for(int i=0;i<n;i++)
   {
       if(isvertex[i])
           vertexnum++;
   }
}
void MainWindow::on_pr_clicked()
{

    inputdialog *id=new inputdialog(rn);
    id->show();
    pflag=1;
}

